package comp_sort;

import java.util.Arrays;
import java.util.Stack;

// 基于比较的排序算法 (递归&非递归)实现
public class Sort {

    // 公用的工具方法
    private static void swap(int[] arr, int i, int j) {
        // 此法虽好 但遇到相同元素交换就不灵了
        if(arr[i] == arr[j]) return ;
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
//        int temp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = temp;
        return;
    }


    // 冒泡 (不优化版)
    public static void BubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
    }


    // 选择排序
    // 将待排序数组分成两个区间
    // 一个有序区间 一个无序区间
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
    }


    // 插入排序
    // 基本思路 向 有序数组中插入新的元素 并且使得原来的有序数组仍然有序
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int pre = i - 1;
            int temp = arr[i];
            while (pre >= 0 && temp < arr[pre]) {
                arr[pre + 1] = arr[pre];
                pre--;
            }// 循环退出时 pre 指向 第一个小于 temp 的
            // 所以此时 pre + 1 就是 temp 的有序位置
            arr[pre + 1] = temp;
        }
    }


    // 希尔排序
    // 放大了插入排序的特性
    // 插入排序的特性
    // 1. 当待数组相对有序 插入排序速度快
    // 2. 当数组中元素不多时 插入排序速度快
    // 希尔排序采用的就是 将 arr 按照 gap 长度进行分组 把数组变小 让后将这些变小的数组变得有序
    // 然后再插入排序
    public static void shellSort(int[] arr) {
        // 把数组分成多组
        int gap = arr.length / 2; // 这个 gap 的范围是 [1,arr.length)
        while (gap > 1) {
            insertSortByGap(arr, gap);
            gap /= 2;
        }
        insertSortByGap(arr, 1);
    }

    private static void insertSortByGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int pre = i - gap;
            while (pre >= 0 && arr[pre] >= temp) {
                arr[pre + gap] = arr[pre];
                pre -= gap;
            }
            arr[pre + gap] = temp;
        }
    }


    // 快速排序 (递归实现)
    // 基本思路 (分治) 找到基准值 确定基准值的(排序后应该在的)位置;
    // 有两个指针 left(找大于 target 的元素 ),right(找小于 target 的元素 ) 和 一个 基准值 target
    // left 初始为 数组 首元素
    // right 初始为 数组 尾部元素
    // 如果是 按照先 移动 left  找大于 target 的元素则
    // 当  left == right 时 left 指向的一定是大于 target 的元素 (为什么说一定是 left == right 时退出循环,而不是 left > right 呢 ？
    // 是因为 right 比 left 后动 当 right 准备动之前 (上一次交换 结束 ) 此时 right 指向的 元素值 > target)
    // 如果是 按照 right 先动 left 后移动
    // 当left == right 退出循环时 right 指向的也是 大于 target 至于是为什么想法同上
    public static void quickSort(int[] arr) {
        // 基准值的左边 [left,right]
        // 为了方便 我们取最后一个元素 作为基准值
        quickHelper(arr, 0, arr.length - 1);
    }

    private static void quickHelper(int[] arr, int left, int right) {
        if (left >= right) return; // 当数组中只有一个元素时 默认有序

        int target = arr[right];
        int index = right;
        int cur_left = left;
        int cur_right = right;
        while (cur_left < cur_right) {
            while (cur_left < cur_right && arr[cur_left] < target) {
                cur_left++;
            }

            while (cur_left < cur_right && arr[cur_right] >= target) {
                cur_right--;
            }
            swap(arr, cur_left, cur_right);
        }
        swap(arr, cur_left, index); // 将 cur_left 换成 cur_right 也是可以的

        // 递归 基准值的左边 右边
        quickHelper(arr, left, cur_left - 1);
        quickHelper(arr, cur_left + 1, right);
    }


    // 快速排序 (非递归实现)
    public static void quickSortByLoop(int[] arr) {
        // 模拟递归场景即可
        Stack<Integer> stack = new Stack<>(); // 这个栈存储的时下标
        int left = 0;
        int right = arr.length - 1;

        stack.push(right); // 先放 right
        stack.push(left); // 后放 left 注意放的顺序 等取得时候要 先取 left 再取 right

        while (!stack.isEmpty()) {
            int cur_left = stack.pop();
            int cur_right = stack.pop();
            int mid = quickByLoopHelper(arr, cur_left, cur_right);
            if (mid == -1) continue; // 判断当前基准值所在位置是否正确
            // 先排基准值左边
            // 再排基准值右边
            stack.push(cur_right);
            stack.push(mid + 1);

            stack.push(mid - 1);
            stack.push(cur_left);
        }
    }

    private static int quickByLoopHelper(int[] arr, int left, int right) {
        // 返回 排序后基准值的下标 为了方便还是取最后一个元素做为基准值
        if (left >= right) return -1;
        int target = arr[right];
        int index = right;
        int cur_left = left;
        int cur_right = right;

        while (cur_left < cur_right) {

            while (cur_left < cur_right && arr[cur_left] < target) {
                cur_left++;
            }

            while (cur_left < cur_right && arr[cur_right] >= target) {
                cur_right--;
            }
            swap(arr, cur_left, cur_right);
        }
        swap(arr, cur_left, index);
        return cur_left; // 这里返回cur_left 或者cur_right 都行
    }


    // 堆排序
    // 有 两种 堆排序的 办法
    // 1. 建立一个堆 ,将堆顶元素依次poll() 空间复杂度为 O(n);
    // 2. 将原来的数组建立一个堆 升序建立大根堆 降序建立小根堆  将堆顶元素依次与堆中最后元素进行交换 并逻辑删除 堆顶 空间复杂度为 O(1)
    // 这里采用第二种
    public static void heapSort(int[] arr) { // 假设是升序排序
        // 以数组arr建立大根堆
        // 从最后一个非叶子节点开始 向下调整大根堆
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            adjustDown(arr, i, arr.length);
        } // 循环完毕 堆就调整完毕

        // 依次交换堆顶与堆尾 逻辑上删除堆尾并进行调整

        int length = arr.length - 1;
        for (; length > 0; length--) {
            swap(arr, 0, length);
            adjustDown(arr, 0, length); // 将数组长度减去 1 逻辑删除队尾
        }

    }

    // 为了方便方法的复用 length 代表堆的实际长度
    private static void adjustDown(int[] arr, int parent, int length) {
        int l_child = 2 * parent + 1;
        while (l_child < length) {

            if (l_child < length - 1 && arr[l_child] < arr[l_child + 1]) {
                l_child++;
            }// 这个判断过后  l_child 一定指向parent的孩子中最大的元素
            // 判断是否需要交换
            if (arr[parent] < arr[l_child]) {
                swap(arr, parent, l_child);
                break;
            }
            // 继续向下调整
            parent = l_child;
            l_child = 2 * parent + 1;
        }
    }


    // 归并排序(递归实现)
    // 适用场景
    // 大规模数据 即 有些数据不在内存中在磁盘中
    // 有序 数组 或者链表的合并
    // 思路 ： 合并有序数组 或 链表
    public static void mergeSort(int[] arr) {
        // 让后将两个有序数组合并
        // 将 两边数组都排好序
        mergeSortHelper(arr, 0, arr.length);

    }

    // [left,right)
    private static void mergeSortHelper(int[] arr, int left, int right) {
        if (right - left <= 1) return;
        int mid = left + (right - left) / 2;
        mergeSortHelper(arr, left, mid);
        mergeSortHelper(arr, mid, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        // 合并区间 [left,mid) , [mid,right)
        int cur1 = left, cur2 = mid, cur = 0;
        int[] temp = new int[right - left];
        while (cur1 < mid && cur2 < right) {
            if (arr[cur1] < arr[cur2]) {
                temp[cur] = arr[cur1];
                cur1++;
                cur++;
            } else {
                temp[cur] = arr[cur2];
                cur++;
                cur2++;
            }
        }// 出了这个循环会出现 某一个区间没有结束

        while (cur1 < mid) {
            temp[cur] = arr[cur1];
            cur++;
            cur1++;
        }

        while (cur2 < right) {
            temp[cur] = arr[cur2];
            cur2++;
            cur++;
        }


        for (int i = 0; i < temp.length; i++) {
            arr[i + left] = temp[i];
        }
    }


    // 归并排序 非递归实现
    public static void mergeSortByLoop(int[] arr) {
        // 类似于 递归 将 数组分成 1 个元素 为 1 份
        //                     2 个元素 为 1 份
        //                     3 个元素 为 1 份
        //                     4 个元素 为 1 份
        //                     arr.length/2 个元素 为 1 份
        for (int gap = 1; gap < arr.length; gap *= 2) { // gap 跨越的范围
            for (int j = 0; j < arr.length; j += gap * 2) { // 范围的初始 值
                int left = j;
                int mid = j + gap;
                if (mid > arr.length) {
                    continue;
                }
                int right = mid + gap;
                if (right > arr.length) {
                    right = arr.length;
                }
                merge(arr, left, mid, right);
            }
        }
    }


    public static void main(String[] args) {
        int[] arr = {8, 3, 5, 7, 7, 9, 2, 1};
        // insertSort(arr);
//        shellSort(arr);
//        quickSortByLoop(arr);
//        selectSort(arr);
//        heapSort(arr);
//        mergeSort(arr);
        mergeSortByLoop(arr);
        System.out.println(Arrays.toString(arr));
    }

}
